package com.ryujung.hash.leetCode_1002;

import java.util.*;

class Solution {

    /**
     * 统计重复的字符，关键在于只要统计每个字符重复的最小次数即可
     */
    public List<String> commonChars(String[] words) {
        int[] minFrq = new int[26];
        Arrays.fill(minFrq, Integer.MAX_VALUE);
        for (String word : words) {
            int[] chs = new int[26];
            // 更新当前words的
            for (char c : word.toCharArray()) {
                chs[c - 'a'] += 1;
            }
            for (int i = 0; i < chs.length; i++) {
                minFrq[i] = Math.min(minFrq[i], chs[i]);
            }
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < minFrq.length; i++) {
            for (int j = 0; j < minFrq[i]; j++) {
                // 创建字符串使用String.valueOf(char ch)
                res.add(String.valueOf((char) ('a' + i)));
            }
        }
        return res;
    }
    // 时间复杂度：O(n*m*|Σ|) Σ为字符集大小
    // 空间复杂度：O(|Σ|)

    /*
     * 时间复杂度：O(n(m+∣Σ∣))，
     * 其中 n 是数组 A 的长度（即字符串的数目），
     * m 是字符串的平均长度，Σ 为字符集，在本题中字符集为所有小写字母，∣Σ∣=26。
     *
     *     遍历所有字符串并计算 freqfreq 的时间复杂度为 O(nm)；
     *     使用freq更新 minfreq 的时间复杂度为 O(n∣Σ∣)；
     *     由于最终答案包含的字符个数不会超过最短的字符串长度，
     *      因此构造最终答案的时间复杂度为O(m+∣Σ∣)。
     *      这一项在渐进意义上小于前二者，可以忽略。
     *
     * 空间复杂度：O(∣Σ∣)，这里只计算存储答案之外的空间。
     * 我们使用了数组 freq 和 minfreq，它们的长度均为∣Σ∣。
     */

    /**
     * 运行失败:
     * Time Limit Exceeded
     * <p>
     * 正确，但是过于繁杂多余
     * 很多无用的字符串生成和操作动作，很差的算法
     */
    public List<String> commonCharsBad(String[] words) {
        Map<String, List<String>> map = new HashMap<>();

        // 遍历每个字符，使用map<Character,List<String>> ,
        // 将包含当前char的word都保存起来
        for (int i = 0; i < words.length; i++) {
            for (Character c : words[i].toCharArray()) {
                int repeatTime = 0;
                String charName = c.toString() + repeatTime;
                List<String> wordsList;
                while ((wordsList = map.getOrDefault(charName, new ArrayList<>())).contains(words[i])) {
                    repeatTime++;
                    charName = c.toString() + repeatTime;
                }
                wordsList.add(words[i]);
                map.put(charName, wordsList);
            }
        }

        List<String> res = new ArrayList<>();
        // 依次取出所有的char所对应的List<String>，
        // 如果内容长度和words相同，就是重复的char
        for (String charName : map.keySet()) {
            List<String> theWordsHaveThisCharList = map.get(charName);
            if (theWordsHaveThisCharList.size() == words.length) {
                res.add(charName.substring(0, 1));
            }
        }
        return res;
    }

}